package cn.corffen.test.algorithm.leetcode.easy.sort;

public class SortAndSearchDemo {

    public static void main(String[] args) {
        testFirstBad();
    }

    private static void testFirstBad() {
        SortAndSearchDemo demo = new SortAndSearchDemo();
        int i = demo.firstBadVersion(5);
        System.out.println("version = " + i);
    }


    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                nums1[k++] = nums1[i++];
            } else {
                nums1[k++] = nums2[j++];
            }
        }
        if (i == m) {
            for (; j < n; j++) {
                nums1[k++] = nums2[j];
            }
        }
        if (j == n) {
            while (i < m) {
                nums1[k++] = nums1[i++];
            }
        }
    }

    /**
     * 123
     * 235
     * 1 2 2 3
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1, 0, nums1_copy, 0, m);
        while (i < m && j < n) {
            nums1[k++] = (nums1_copy[i] < nums2[j]) ? nums1_copy[i++] : nums2[j++];
        }
        if (i < m) {
            System.arraycopy(nums1_copy, i, nums1, i + j, m + n - i - j);
        }
        if (j < n) {
            System.arraycopy(nums2, j, nums1, i + j, m + n - i - j);
        }
    }

    //跟高楼摔鸡蛋是一个问题

    /**
     * @param n
     * @return
     */
    public int firstBadVersion(int n) {
        int lo = 1;
        int hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public boolean isBadVersion(int n) {
        return n >= 4;
    }
}
